package com.shuzijun.leetcode.editor.cn;

import java.util.Stack;

public class TrappingRainWater{
    public static void main(String[] args) {
         Solution solution = new TrappingRainWater().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        public int trap(int[] height) {
            int n = height.length;
            int result = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                if (stack.isEmpty()){
                    stack.push(i);
                    continue;
                }

                while (!stack.isEmpty()){
                    Integer top = stack.peek();
                    if (height[top] >= height[i]){
                        stack.push(i);
                        break;
                    }else {
                        top = stack.pop();
                        if (stack.isEmpty()){
                            stack.push(i);
                            break;
                        }
                        Integer left = stack.peek();
                        int h = Math.min(height[left],height[i] )-height[top];
                        int w = i-left-1;
                        result += h*w;
                    }
                }
            }
            return result;
        }
//    public int trap(int[] height) {
//        int n = height.length;
//        int result = 0;
//
//        for (int i = 1; i < n - 1; i++) {
//            int ln = 0;
//            for (int j = 0; j < i; j++) {
//                if (height[j] > ln) ln = height[j];
//            }
//
//            int rn = 0;
//            for (int j = i+1; j < n; j++) {
//                if (height[j] > rn) rn = height[j];
//            }
//            int carry = Math.min(ln,rn) - height[i];
//            if (carry < 0) carry = 0;
//            result += carry;
//        }
//        return result;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

}